package 笔试2.网易.two;

import org.junit.Test;

import java.util.*;

//bs-map层序
public class Main {

    static Map<Integer, List<Integer>> map =new HashMap<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        List<int[][]> glist =new ArrayList<>();
        int[][] t=new int[T][2];
        for (int i = 0; i < T; i++) {
            int max=sc.nextInt();
            int M1 = sc.nextInt();
            int M2 = sc.nextInt();
            t[i][0]=max; t[i][1]=M2;
            int[][] g= new int[M1+M2][2];
            for (int j = 0; j < M1+M2; j++) {
                g[j][0]=sc.nextInt();
                g[j][1]=sc.nextInt();
            }
            glist.add(g);
        }
        //shuruover

        for (int i = 0; i < glist.size(); i++) {
            f(glist.get(i),t,i);
        }
    }

    private static void f(int[][]g, int[][] t, int ci){
        fangrumap(g);

        List<int[]> namaxyong = new ArrayList<>();
        for (int[] ints : g) {
            namaxyong.add(ints);
        }
        Collections.sort(namaxyong, (a,b)->a[0]-b[0]);
        int max = namaxyong.get(namaxyong.size()-1)[0];
        Collections.sort(namaxyong, (a,b)->a[1]-b[1]);
        max = Math.max(max,namaxyong.get(namaxyong.size()-1)[0]);
//        System.out.println("M"+max);

        //层序
        Queue<Integer> que = new LinkedList<>();
        que.add(1);
        int sp=1;
        while (!que.isEmpty()){
            int oldsz = que.size();
            for (int i = 0; i < oldsz; i++) {
                Integer poll = que.poll();
//                System.out.println("cur"+poll);
//                if(map.get(poll).contains(max)){
                if(map.get(poll).contains(t[ci][0])){
                    if(sp/2 <= t[ci][1]){
                        System.out.println(sp/2);
                        return;
                    }else{
                        System.out.println(sp - t[ci][1]);
                        return;
                    }
                }

                List<Integer> list = map.get(poll);
                for (Integer num : list) {
                    que.add(num);
                }
            }
            sp++;
        }

        //不执行
        return;
    }

    private static void fangrumap(int[][] g) {
        for (int i = 1; i <= g.length; i++) {
            map.put(i,new ArrayList<Integer>());
        }
        for (int i = 0; i < g.length; i++) {
            int a=g[i][0],b=g[i][1];
            map.get(b).add(a);
        }
    }

//    @Test
//    public void test() {
//        int[][] g = {
//                {5,4},
//                {5,2},
//                {6,3},
//                {6,2},
//                {8,6},
//                {8,4},
//                {3,4},
//                {2,4},
//                {1,4},
//                {2,1},
//                {3,1},
//                {5,7},
//                {2,8}
//        };
//
////        int[][] g ={
////                {5,3},
////                {7,3},
////                {7,8},
////                {9,8},
////                {2,6},
////                {6,8},
////                {1,4},
////                {4,3},
////                {5,7},
////                {9,2},
////                {2,1},
////                {4,8},
////                {3,5},
////                {6,1}
////
////        };
//
//        fangrumap(g);
//
//        List<int[]> namaxyong = new ArrayList<>();
//        for (int[] ints : g) {
//            namaxyong.add(ints);
//        }
//        Collections.sort(namaxyong, (a,b)->a[0]-b[0]);
//        int max = namaxyong.get(namaxyong.size()-1)[0];
//        Collections.sort(namaxyong, (a,b)->a[1]-b[1]);
//        max = Math.max(max,namaxyong.get(namaxyong.size()-1)[0]);
////        System.out.println("M"+max);
//
//        //层序
//        Queue<Integer> que = new LinkedList<>();
//        que.add(1);
//        int sp=1;
//        while (!que.isEmpty()){
//            int oldsz = que.size();
//            for (int i = 0; i < oldsz; i++) {
//                Integer poll = que.poll();
////                System.out.println("cur"+poll);
//                if(map.get(poll).contains(max)){
//                    System.out.println(sp/2);
//                    return;
//                }
//
//                List<Integer> list = map.get(poll);
//                for (Integer num : list) {
//                    que.add(num);
//                }
//            }
//            sp++;
//        }
//
//
//        //不执行
//        return;
//    }
}
/*
2
8 11 2
5 4
6 3
8 6
6 2
5 7
3 4
2 4
5 2
2 1
3 1
2 8
8 4
1 4
9 8 7
5 3
7 3
7 8
9 8
2 6
6 8
1 4
4 3
5 7
9 2
2 1
4 8
3 5
6 1
2 8
 */